package com.onepiece.shipelves.common.myutils.heap;

//建堆复杂度为n，堆排序复杂度为nlogn,非稳定排序
public class Heap {
    private int[] nums;
    private int n;
    private int count;

    public Heap(int capacity) {
        nums = new int[capacity + 1];
        n = capacity;
        count = 0;
    }


    private static void swap(int[] nums, int i, int j){
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

    //插入的元素放到最后，然后从下往上堆化
    public void insert(int data){
        if(count >= n) return;
        ++count;//这里先加，是因为数组第一位不存放数据，所以capacity是+1的
        nums[count] = data;
        int i = count;
        //如果插入的元素比它的父节点大，就将他们交换,然后判断已交换的父节点是否比它的父节点还要大，继续堆化
        while (i / 2 > 0 && nums[i] > nums[i/2]){
            swap(nums, i, i/2);
            i = i/2;
        }
    }

    //移除堆顶元素的过程，需要把最后的元素放到堆顶，然后再进行从上往下的堆化就可以继续满足完全二叉树的特征
    public void removeMax(){
        if(count == 0) return;
        nums[1] = nums[count];
        --count;
        heapify(nums, count, 1);
    }

    //从上往下堆化，i代表从哪个节点开始向下堆化，这里比较当前节点是否比它的左右节点小，如果小就进行交互，然后继续往下堆化，如果没有左右节点就break
    private static void heapify(int[] nums, int count, int i) {
        while (true){
            int maxPos = i;
            if(i * 2 < count && nums[i] < nums[i * 2])maxPos = i * 2;
            if(i * 2 + 1 < count && nums[maxPos] < nums[i * 2 + 1])maxPos = i * 2 + 1;
            if(maxPos == i)break;
            swap(nums, i, maxPos);
            i = maxPos;
        }

    }

    //
    //建堆之后，把最大的顶部的节点和最后一个节点交换，然后把最后的那个数排除出堆化的过程，然后进行堆化，这样最后得到的nums就是排序好的
    //就是不停的把最大数移到数组末尾，然后堆化最上面的节点
    public static void sort(int[] nums, int n){
        buildHeap(nums, n);
        int k = n;
        while (k > 1){
            swap(nums, 1, k);
            --k;
            heapify(nums, k, 1);
        }
    }

    //采用从上往下堆化，因为叶子节点没有子节点不需要堆化，所以选择n/2的位置的父节点向下堆化，不需要向上堆化，所以比较交换次数最少
    //也可以采用上面的insert方法，顺序遍历数组进行插入堆化
    private static void buildHeap(int[] nums, int n) {
        for (int i = n/2; i >= 1; --i) {
            heapify(nums, n, i);
        }
    }

    public static void main(String[] args) {

        //这里第一位要加一个数字,这个用数组表示树的时候，第一位空出来有助于后面通过父节点查找子节点和子节点查找父节点
        int[] nums = {999,1,2,3,5,2,6,9,3,2,1};
        sort(nums, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }
}
